/*  动态规划解题关键在于冷静分析问题，找出问题的规律。唉，积累经验吧 */

/**
 * 1.跳跃游戏
 * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个下标。
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    // 实时维护每一步最远跳跃位置
    let rightJump = 0,  
        len = nums.length;
    for (let i = 0; i < len; i++) {
        if (i <= rightJump) {
            rightJump = Math.max(rightJump, i + nums[i]);
            if (rightJump >= len - 1) {
                return true;
            }
        } else { // 从零开始的最远跳跃不能抵达当前位置
            return false;
        }
    }
};
// console.log('canJump:', canJump([2,3,1,1,4])); // true
// console.log('canJump:', canJump([3,2,1,0,4])); // false
// console.log('canJump:', canJump([0])); // true
/**
 * 2.不同路径
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？
 * 公式：fn[i][j] = fn[i-1][j] + fn[i][j-1];当i=0 fn[i][j] = fn[i][j-1];当j=0 fn[i][j] = fn[i - 1][j]
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    let res = new Array(m);
    res[0] = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {
        let arr = new Array(n);
        arr[0] = 1;
        res[i] = arr;
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            res[i][j] = res[i - 1][j] + res[i][j - 1];
        }
    }
    return res[m - 1][n - 1];
};
// console.log('uniquePaths:', uniquePaths(3, 2)); // 3
// console.log('uniquePaths:', uniquePaths(3, 3)); // 6
// console.log('uniquePaths:', uniquePaths(3, 7)); // 28
/**
 * 3.零钱兑换
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 * 你可以认为每种硬币的数量是无限的。
 * 公式: fn(amount) = min(fn(amount - coins[0]), ..., fn(amount - coins[coins.length - 1])) + 1;
 * 注意: 这道题只使用公司解题还不够，执行时间远远超出限制。需要对结果进行缓存。
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    function dfs(coins, amount, memory) {
        if (amount === 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        if (memory[amount]) {
            return memory[amount];
        }
        let min = Number.MAX_SAFE_INTEGER;
        for (const c of coins) {
            let count = dfs(coins, amount - c, memory) + 1;
            if (count > 0 && count < min) {
                min = count;
            }
        }
        memory[amount] = min === Number.MAX_SAFE_INTEGER ? -1 : min;
        return memory[amount];
        // return min === Number.MAX_SAFE_INTEGER ? -1 : min;
    }
    return dfs(coins, amount, []);
};
// console.log('coinChange:', coinChange([1, 2, 5], 38));
// console.log('coinChange:', coinChange([186,419,83,408], 6249));
/**
 * 4.最长上升子序列
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let len = nums.length,
        dp = new Array(len).fill(1),
        maxAns = 1;
    for (let i = 1; i < len; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxAns = Math.max(maxAns, dp[i]);
    }
    return maxAns;
};
// console.log(lengthOfLIS([7,7,7,7,7,7])); // 1
// console.log(lengthOfLIS([0,1,0,3,2,3])); // 4
// console.log(lengthOfLIS([4,10,4,3,8,9])); // 3
// console.log(lengthOfLIS([1,3,6,7,9,4,10,5,6])); // 6
